# 完全背包问题

class Solution:
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # n = len(nums)

        f = [0] * (target + 1)
        f[0] = 1

        for i in range(1, target + 1):
            for j in nums:
                if j <= i:
                    f[i] += f[i - j]
        return f[-1]


nums = [1, 2, 3]
target = 4
s =Solution()
m = s.combinationSum4(nums,target)
print(m)